package org.getOffer.offer26;

/**
 * @Author yu
 * @Date 2021/10/7
 */
public class Solution {

    public static void main(String[] args) {
        
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(9);
        TreeNode treeNode3 = new TreeNode(20);
        TreeNode treeNode4 = new TreeNode(15);
        TreeNode treeNode5 = new TreeNode(7);

        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;

        TreeNode treeNode6 = new TreeNode(20);
        TreeNode treeNode7 = new TreeNode(15);
        TreeNode treeNode8 = new TreeNode(7);

        treeNode6.left = treeNode7;
        treeNode6.right = treeNode8;

        Solution solution = new Solution();

        System.out.println(solution.isSubStructure(treeNode1, treeNode6));

    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (this.recur(A, B) || this.isSubStructure(A.left, B) || this.isSubStructure(A.right, B));
    }

    public boolean recur(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null || A.val != B.val) {
            return false;
        }
        return this.recur(A.left, B.left) && this.recur(A.right, B.right);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}